package com.kizuki.algorithm.offer;

import java.util.*;

public class Solution {

    public boolean Find(int target, int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        int maxI = array.length;
        int maxJ = array[0].length;
        int i = maxI - 1, j = 0;
        while (i >= 0 && j < maxJ) {
            if (target == array[i][j]) {
                return true;
            } else if (target > array[i][j]) {
                j++;
            } else {
                i--;
            }
        }
        return false;
    }

    /**
     * 空间复杂度O(n) java没办法避免new 暂时也没想到更好的办法
     */
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        for (int i = 0, len = s.length(); i < len; i++) {
            if (s.charAt(i) == ' ') {
                res.append("%20");
            } else {
                res.append(s.charAt(i));
            }
        }
        return res.toString();
    }

    class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null) {
            return new ArrayList<>(0);
        }
        ArrayList<Integer> res = new ArrayList<>();
        while (listNode != null) {
            res.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(res);
        return res;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode reConstructBinaryTree1(int[] pre, int[] in) {
        if (in.length == 0 || pre.length == 0) {
            return null;
        }
        int len = pre.length;
        TreeNode treeNode = new TreeNode(pre[0]);
        for (int i = 0; i < len; i++) {
            if (in[i] == pre[0]) {
                treeNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                treeNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, len), Arrays.copyOfRange(in, i + 1, len));
            }
        }
        return treeNode;
    }

    /**
     * 不copy 难点在边界处理
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return binaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    private TreeNode binaryTree(int[] pre, int preLeft, int preRight, int[] in, int inLeft, int inRight) {
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        TreeNode treeNode = new TreeNode(pre[preLeft]);
        for (int i = inLeft; i <= inRight; i++) {
            if (pre[preLeft] == in[i]) {
                treeNode.left = binaryTree(pre, preLeft + 1, preLeft + i - inLeft, in, inLeft, i - 1);
                treeNode.right = binaryTree(pre, preLeft + i - inLeft + 1, preRight, in, i + 1, inRight);
            }
        }
        return treeNode;
    }

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0) {
            return 0;
        }
        int left = 0, right = array.length - 1;
        while (left < right) {
            if (array[left] < array[right]) {  // 说明此事 left到right是递增的
                return array[left];
            }
            int mid = (left + right) >> 1;
            if (array[mid] > array[right]) {  // 右半区非递增, 因为已知找最小值, 所以可以直接过滤array[mid]
                left = mid + 1;
            } else if (array[mid] < array[right]) {  // 右半区递增，直接舍去右半区
                right = mid;
            } else {    // 不清楚左半区还是右半区, 选择一个方向逼近
                right--;
//                left++;
            }
        }
        return array[left];
    }

    /**
     * 斐波那契 非递归和递归
     */
    public int Fibonacci(int n) {
        if (n < 2 ) {
            return n;
        }
        int f0 = 0, f1 = 1, fn = 0;
        for (int i = 2; i <= n; i++) {
            fn = f0 + f1;
            f0 = f1;
            f1 = fn;
        }
        return fn;
    }

    public int rectCover(int target) {
        if (target <= 2 ) {
            return target;
        }
        return rectCover(target - 1) + rectCover(target - 2);
    }


    /**
     * 位运算都是补码来运算
     * << 正负数都是位左移，最右边补0
     * >> 右移，最左边正数补0，负数补1
     * >>> 右移，最左边正数负数都补0
     */
    // 常规解法
    public int NumberOf1(int n) {
        int count = 0;
        int m = 0x01;
        while(m != 0) {
            if ((m & n) == m) {
                count ++;
            }
            m <<= 1;
        }
        return count;
    }

    // 注意>> 和 >>> 的区别
    public int NumberOf12(int n) {
        int m = 0x01;
        int count = 0;
        while(n != 0) {
            if ((n & m) == m) {
                count ++;
            }
            n >>>= 1;
        }
        return count;
    }

    public int NumberOf13(int n) {
        int count = 0;
        while(n != 0) {
            count ++;
            n &= (n - 1);
        }
        return count;
    }

    /**
     * 将exponent拆分成二进制 O(logN)
     */
    public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1.0;
        }
        if (exponent < 0) {   // 保证exponent是正整数
            base = 1 / base;
            exponent = -exponent;
        }
        double temp = base;
        double result = 1.0;
        while(exponent != 0) {
            if ((exponent & 1) == 1) {
                result *= temp;
            }
            temp *= temp;
            exponent >>= 1;
        }
        return result;
    }

    /**
     * 时间复杂度和空间复杂度都是 O(n)
     */
    public int[] reOrderArray (int[] array) {
        int length = array.length;
        if (length == 0) {
            return array;
        }
        int[] result = new int[length];
        int pos = 0;
        for (int value : array) {
            if (value % 2 == 1) {
                result[pos++] = value;
            }
        }
        for (int value : array) {
            if (value % 2 == 0) {
                result[pos++] = value;
            }
        }
        return result;
    }

    /**
     * 快慢指针
     * 边界可以在脑中想个简单例子
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(k > 0) {
            if (fast == null) { // 边界
                return null;
            }
            fast = fast.next;
            k--;
        }
        while(fast != null) {  // 边界
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public ListNode Merge(ListNode list1,ListNode list2) {
        // 一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱结点。
        ListNode merge = new ListNode(0);
        ListNode cur = merge;
        while(list1 != null && list2 != null) {
            if (list1.val >= list2.val) {
                cur.next = list2;
                list2 = list2.next;
            } else {
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        if (list1 == null) {
            cur.next = list2;
        }
        if (list2 == null) {
            cur.next = list1;
        }
        return merge.next;
    }


    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return isContain(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    // 判断root1是否包含root2
    boolean isContain(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        return root1.val == root2.val && isContain(root1.left, root2.left) && isContain(root1.right, root2.right);
    }

    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null) {
            return null;
        }
        TreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }

    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        int up = 0;
        int down = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        while(true) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[up][i]);
            }
            if (++up > down) {
                return res;
            }
            for (int i = up; i <= down; i++) {
                res.add(matrix[i][right]);
            }
            if (--right < left) {
                return res;
            }
            for (int i = right; i >= left; i--) {
                res.add(matrix[down][i]);
            }
            if (--down < up) {
                return res;
            }
            for (int i = down; i >= up; i--) {
                res.add(matrix[i][left]);
            }
            if (++left > right) {
                return res;
            }
        }
    }

    // 模拟栈的操作
    public boolean IsPopOrder(int [] pushA, int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int j = 0;
        while (i < pushA.length) {
            if (pushA[i] != popA[j]) {
                stack.push(pushA[i]);
                i++;
            } else {
                i++;
                j++;
                while(j < popA.length && !stack.isEmpty() && popA[j] == stack.peek()) {
                    stack.pop();
                    j++;
                }
            }
        }
        return stack.empty();
    }

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        ArrayList<TreeNode> queue = new ArrayList<>();
        queue.add(root);
        while(queue.size() > 0) {
            TreeNode remove = queue.remove(0);
            res.add(remove.val);
            if (remove.left != null) {
                queue.add(remove.left);
            }
            if (remove.right != null) {
                queue.add(remove.right);
            }
        }
        return res;
    }

    // todo 暂时不想做二叉树的
    public boolean VerifySquenceOfBST(int [] sequence) {
        return false;
    }

    public int MoreThanHalfNum_Solution(int [] array) {
        int cnt = 0;
        int maxCntValue = 0;
        for (int value : array) {
            if (cnt == 0) {
                maxCntValue = value;
                cnt ++;
            } else {
                cnt += (maxCntValue == value ? 1:-1);
            }
        }
        // 如果有出现超过一半的数则是maxCntValue，但是不一定存在这个超过一半的数
        // eg:[2, 2, 3, 4, 1]  maxCntValue = 1
        cnt = 0;
        for (int value : array) {
            if (value == maxCntValue) {
                cnt ++;
            }
        }
        return cnt > array.length / 2 ? maxCntValue : 0;
    }

    // 虾皮链表排序-递归版本
    public ListNode sortList(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        return merge(left, right);
    }

    // 非递归版本
    public ListNode sortList1(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }
        int len = 0;
        ListNode countHead = head;
        while(countHead != null) {
            len ++;
            countHead = countHead.next;
        }

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        for(int perTakeNum = 1; perTakeNum < len; perTakeNum <<= 1) {
            ListNode prev = dummyHead;
            ListNode cur = dummyHead.next;

            while(cur != null) {
                ListNode list1 = cur;
                for (int i = 1; i < perTakeNum && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }

                ListNode list2 = cur.next;
                cur.next = null;
                cur = list2;
                for (int i = 1; i < perTakeNum && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }

                ListNode next = null;
                if (cur != null) {
                    next = cur.next;
                    cur.next = null;
                }
                ListNode mergedList = merge(list1, list2);
                prev.next = mergedList;
                while(prev.next != null) {
                    prev = prev.next;
                }
                cur = next;
            }
        }
        return dummyHead.next;
    }

    public ListNode merge(ListNode left, ListNode right){
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        if (left != null) {
            cur.next = left;
        }
        if (right != null) {
            cur.next = right;
        }
        return head.next;
    }



    public static void main(String[] args) {
        new Solution().MoreThanHalfNum_Solution(new int[]{2, 2, 3, 4, 1});
    }

}

class Solution1{

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        stack.push(node);
        if (minStack.isEmpty()) {
            minStack.push(node);
        } else {
            Integer peek = minStack.peek();
            int pushNode = peek < node ? peek : node;
            minStack.push(pushNode);
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }

}
